import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Graph{
    // parameter ： point number(n)/ adjacency list(adj)
    private int n;
    // LinkedList's Array
    private LinkedList<Integer> adj[];
    //constructor
    public Graph(int n){
        this.n=n;
        adj=new LinkedList[n];
        for(int i=0;i<n;i++){
            adj[i]=new LinkedList();
        }
    }
    //the function to add the edge
    //no direction
    void addEdge(int v,int w){
        adj[v].add(w);
        adj[w].add(v);
    }
    //BFS（breadth first search）
    void BFS(int s){ // s is head point
        boolean visited[] =new boolean[n]; //record if the point is visited
        Queue<Integer> queue=new LinkedList<>();
        visited[s]=true; // head point is recorded
        queue.add(s);

        while(!queue.isEmpty()){
            s=queue.poll(); //visit the element which is polled
            System.out.print(s + " "); //print

            for(int i :adj[s]){

                if(!visited[i]){
                    visited[i]=true;
                    queue.add(i);
                }
            }
        }
    }

    //DFS(depth first search)
    void DFS(int s){
        boolean visited[] =new boolean[n];
        Stack<Integer> stack =new Stack<>();
        visited[s]=true;
        stack.add(s);

        while(!stack.isEmpty()){
            s= stack.pop();
            System.out.print(s+" ");

            for(int i:adj[s]){
                if(!visited[i]){
                    visited[i]=true;
                    stack.add(i);
                }
            }
        }
    }

// because visited[] is created specially,the point must start from 0 successively
    public static void main(String[] args) {
        Graph g= new Graph(6);

        g.addEdge(0,1);
        g.addEdge(0,2);
        g.addEdge(1,2);
        g.addEdge(1,3);
        g.addEdge(1,4);
        g.addEdge(3,4);
        g.addEdge(2,5);

        System.out.println("BFS:");
        g.BFS(0);
        System.out.println();
        System.out.println("DFS:");
        g.DFS(0);

    }
}